The present invention is directed to storage memory in a data processing system and/or a network of computers. More particularly, the invention is directed to methods and apparatus for making replacement decisions for data objects in such a system and/or network.
The conservation and efficient utilization of memory space are important for storage units. Although space is a significant consideration for general memory, it is most critical in space limited temporary, short or long term memory buffers. For example, in many data processing systems there is provided between the working store of the central processing unit and the main store, a high speed memory unit which is commonly called a xe2x80x98cachexe2x80x99. This unit enables relatively fast access to a subset of data that was previously transferred from main storage to the cache. The main storage is usually either slower speed memory or hard disk storage. This improves the speed of operation of the data processing system. Similarly, in a network of computers caches are used to provide relatively fast access to data that was previously transferred from a distant networked computer. The distant network computer is generally an intermediate proxy computer or an originating web server computer. The Internet is such a network of computers.
To enable retrieval of information from the cache, a xe2x80x98directoryxe2x80x99 of cache entries is maintained. Each data object residing in the cache has its address stored in the directory. Once the cache is filled-up, new data objects can only be entered if one or more old data objects are removed or, as is the subject of this invention, one or more old data objects are reduced in size. Certain procedures are necessary to select objects as candidates for replacement, and to update the directory after a change of cache contents.
A number of systems are known in the art that use cache stores and provide a mechanism for replacement selection and directory updating. For example, U.S. Pat. No. 4,322,795 to R. E. Lange et al., discloses a cache memory arrangement using a least recently used (LRU) scheme for selecting a cache location in which to store data fetched from main memory upon a cache miss.
Several methods are known for finding objects to replace. This includes, for example, the methods given in a paper by Aggarwal et al, entitled, xe2x80x9cOn Caching Policies for Web Objects,xe2x80x9d IBM Research Report 20619, November 1996 (revised March 1997), which is herein incorporated by reference in its entirety. These methods provide alternative ways for choosing which data object or objects to remove instead of replacing the least recently used object. In particular, some of these methods consider factors such as object size in making the choice of objects to replace.
U.S. Pat. No. 5,043,885 to J. Robinson, also discloses a method for making non-LRU replacement choices based on reference counts that are maintained in specific ways. It is herein incorporated by reference.
None of these methods refers to or makes use of multiple resolution versions of a single object. Indeed, these alternative methods of finding objects to replace can be incorporated into an embodiment of the current invention, as subsequently presented, in straightforward ways.
The present invention is for a method, apparatus and article of manufacture for conserving memory space. A method provides for dynamically reducing the resolution of a multiresolution object. It provides mechanisms for reintegrating a dynamically reduced object back into the ordered-list of candidate replaceable objects and for managing multiple resolution levels of the same object. Also provided are procedures through which one computer can request a given resolution level of an object from another computer.
In an embodiment of the present invention a data object is being retrieved over a communication network, usually with some delay, and stored at an intermediate memory either in a proxy or a web browser or both. When the data object is first retrieved, a low resolution version of the object that does not previously exist is computed and saved with the high resolution version. In some cases, this is accomplished with very little additional work. Alternatively, a low resolution version of the object is computed prior to the deletion of a previously stored full resolution version. This last method is particularly useful in situations in which the data conversion is computationally inexpensive. Typically, a low resolution version would require an order of magnitude less storage space than the full resolution version.
In an apparatus implementing this method, when a memory hit is made to a low resolution version of a data object, the low resolution nature of the data object can be identified to the user or application by various means. For example, in a web browsing context in which an image is represented in low resolution format, graphical indicators like a special enclosing box is used. A user then performs a mouse click to retrieve the full resolution version. In other contexts, the data is explicitly labelled as a lower resolution version along with the degree of degradation.
The present invention also includes features applicable for storage on an article of manufacture. For example, the article may take the form of one or more floppy disks insertable into a computer. This will provide the system in which it is used with the attributes of the present invention.